package com.wc.alorithm_blue_bridge._DFS.迷宫;

import java.util.Arrays;

/**
 * @Author congge
 * @Date 2023/10/10 18:37
 * @description 迷宫
 * https://www.lanqiao.cn/problems/602/learning/?page=2&first_category_id=1&sort=students_count&second_category_id=3
 */
public class Main {
    public static void main(String[] args) {
        String map = "01010101001011001001010110010110100100001000101010\n" +
                "00001000100000101010010000100000001001100110100101\n" +
                "01111011010010001000001101001011100011000000010000\n" +
                "01000000001010100011010000101000001010101011001011\n" +
                "00011111000000101000010010100010100000101100000000\n" +
                "11001000110101000010101100011010011010101011110111\n" +
                "00011011010101001001001010000001000101001110000000\n" +
                "10100000101000100110101010111110011000010000111010\n" +
                "00111000001010100001100010000001000101001100001001\n" +
                "11000110100001110010001001010101010101010001101000\n" +
                "00010000100100000101001010101110100010101010000101\n" +
                "11100100101001001000010000010101010100100100010100\n" +
                "00000010000000101011001111010001100000101010100011\n" +
                "10101010011100001000011000010110011110110100001000\n" +
                "10101010100001101010100101000010100000111011101001\n" +
                "10000000101100010000101100101101001011100000000100\n" +
                "10101001000000010100100001000100000100011110101001\n" +
                "00101001010101101001010100011010101101110000110101\n" +
                "11001010000100001100000010100101000001000111000010\n" +
                "00001000110000110101101000000100101001001000011101\n" +
                "10100101000101000000001110110010110101101010100001\n" +
                "00101000010000110101010000100010001001000100010101\n" +
                "10100001000110010001000010101001010101011111010010\n" +
                "00000100101000000110010100101001000001000000000010\n" +
                "11010000001001110111001001000011101001011011101000\n" +
                "00000110100010001000100000001000011101000000110011\n" +
                "10101000101000100010001111100010101001010000001000\n" +
                "10000010100101001010110000000100101010001011101000\n" +
                "00111100001000010000000110111000000001000000001011\n" +
                "10000001100111010111010001000110111010101101111000";

//        map = "010000\n" +
//                "000100\n" +
//                "001001\n" +
//                "110000";
        /**
         * 处理输入
         */
        String[] rows = map.split("\\n");

        int m = rows.length;
        int n = rows[0].length();

        char[][] maze = new char[m][n];

        for (int i = 0; i < m; i++) {
            maze[i] = rows[i].toCharArray();
        }
        /**
         * 打印迷宫
         */
//        for (int i = 0; i < m; i++) {
//            System.out.println(Arrays.toString(maze[i]));
//        }


        /**
         * 建造dp用于计算最短路径
         * dp[i][j] 存储从0 0 ->  i j 的最小步数
         */

        int[][] dp = new int[m][n];
        int max = m * n + 1;

        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], max);
        }

        Main main = new Main();
        main.deepScan(maze, dp, 0, 0, 1);
        /**
         * 打打印dp
         */
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.printf("%6d", dp[i][j]);
//            }
//            System.out.println();
//        }
        /**
         * 记录所有路径
         */
        char[] path = new char[dp[m - 1][n - 1] - 1];

        main.searchPath(dp, 0, 0, path, -1, 'Q');

        /**
         * 打印path
         */
//        System.out.println(Arrays.toString(path));
        String ans = new String(path);

        System.out.println(ans);
    }


    /**
     * 深度检索
     *
     * @param maze 迷宫
     * @param dp
     * @param i    当前行
     * @param j    当前列
     * @param step 当前步数
     */
    public void deepScan(char[][] maze, int[][] dp, int i, int j, int step) {
        int up = i - 1;
        int down = i + 1;
        int left = j - 1;
        int right = j + 1;
        dp[i][j] = Math.min(step, dp[i][j]);

        /**
         * 向上递归
         */
        if (isNotBorder(maze, up, j) && maze[up][j] == '0' && dp[i][j] < dp[up][j]) {
            deepScan(maze, dp, up, j, step + 1);
        }

        /**
         * 向右递归
         */
        if (isNotBorder(maze, i, right) && maze[i][right] == '0' && dp[i][j] < dp[i][right]) {
            deepScan(maze, dp, i, right, step + 1);
        }

        /**
         * 向左递归
         */
        if (isNotBorder(maze, i, left) && maze[i][left] == '0' && dp[i][j] < dp[i][left]) {
            deepScan(maze, dp, i, left, step + 1);
        }

        /**
         * 向下递归
         */
        if (isNotBorder(maze, down, j) && maze[down][j] == '0' && dp[i][j] < dp[down][j]) {
            deepScan(maze, dp, down, j, step + 1);
        }
    }

    /**
     * 搜索路径
     * @param dp
     * @param i 当前行
     * @param j 当前列
     * @param path 存储路径
     * @param index 当前位置
     * @param direction 从哪个方向到达 i j
     * @return 是否走通
     */
    public boolean searchPath(int[][] dp, int i, int j, char[] path, int index, char direction) {
        int downBorder = dp.length - 1;
        int rightBorder = dp[0].length - 1;

        if (i == downBorder && j == rightBorder) {
            path[index] = direction;
            return true;
        }

        int up = i - 1;
        int down = i + 1;
        int left = j - 1;
        int right = j + 1;
        /**
         * flg 表示 当前通路是否直接到达终点
         */
        boolean flg = false;

        /**
         * 注意字典序 D < L < R < U
         */
        /**
         * 向下走
         */
        if (isNotBorder2(dp, down, j) && dp[i][j] + 1 == dp[down][j]) {
            flg = searchPath(dp, down, j, path, index + 1, 'D');

            /**
             * 只要向下走通就无需再走了
             */
            if (flg && index != -1) {
                path[index] = direction;
                return true;
            }
        }

        /**
         * 向左走
         */
        if (isNotBorder2(dp, i, left) && dp[i][j] + 1 == dp[i][left]) {
            flg = searchPath(dp, i, left, path, index + 1, 'L');
            if (flg && index != -1) {
                path[index] = direction;
                return true;
            }
        }

        /**
         * 向右走
         */
        if (isNotBorder2(dp, i, right) && dp[i][j] + 1 == dp[i][right]) {
            flg = searchPath(dp, i, right, path, index + 1, 'R');
            if (flg && index != -1) {
                path[index] = direction;
                return true;
            }
        }

        /**
         * 向上走
         */
        if (isNotBorder2(dp, up, j) && dp[i][j] + 1 == dp[up][j]) {
            flg = searchPath(dp, up, j, path, index + 1, 'U');
            if (flg && index != -1) {
                path[index] = direction;
                return true;
            }
        }

        return flg;
    }

    public boolean isNotBorder(char[][] array, int i, int j) {
        return i >= 0 && j >= 0 && i < array.length && j < array[0].length;
    }

    public boolean isNotBorder2(int[][] array, int i, int j) {
        return i >= 0 && j >= 0 && i < array.length && j < array[0].length;
    }
}
